home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d26 / aaalife.arc / AAALIFE.C next >
Text File  |  1989-07-12  |  19KB  |  514 lines
  1.  
  2. /*  This is an implementation of Conway's Life simulation
  3.     using an algorithm hinted at by J. Francis, in Usenet's
  4.     rec.games.programmer on Jan 25, 1988.
  5.  
  6.                            by
  7.  
  8.     *****************************************************
  9.     *                     Copyright 1989                *
  10.     *  Anibal Antonio Acero         (312) 702-7234      *
  11.     *  5513 S. Everett Ave.     acero@tank.uchicago.edu *
  12.     *  Chicago, IL 60637         ace3@tank.uchicago.edu *
  13.     *                                                   *
  14.     *          LIFE for IBM PC/AT ver 1.0               *
  15.     *                  May 11, 1989                     *
  16.     *  compiled with Borland's TurboC ver. 1.5          *
  17.     *                                                   *
  18.     *****************************************************
  19.  
  20.  
  21. */
  22.  
  23. /*       The following is the Turbo C source code to a fast implementation
  24.     of Life. It tracks the fate of the famous r-pentomino (1103 generations) in
  25.     under 2 minutes on a 12 MHz AT clone.  The excutable included with
  26.     this code supports CGA, EGA, VGA and Hercules graphics. 128K RAM is
  27.     the minimum required.  A filename can be specified on the commandline
  28.     which contains the X,Y coordinates of cells in the starting con-
  29.     figuration. RPENT.LIF is included as an example; it has the coordinates
  30.     for 4 r-pentominoes.  The decision "engine" comes from the Usenet article
  31.     mentioned above. I have a copy I can mail to anyone interested.  Feel free
  32.     to modify or improve upon this; I would appreciate it if you would mail any
  33.     improvements or optimizations so I could incorporate them in later versions.
  34.     Enjoy! (but use at your own risk; all standard disclaimers apply; this
  35.     program has been tested on EGA/286 and VGA/386 machines, the graphics
  36.     drivers are those provided by Borland's Turbo C v. 1.5; it SHOULD work)
  37.  
  38.     A few words on the idiosyncrasies of this version.  The "world" is "spherical".
  39.     If a glider goes out the bottom it will reappear at the top of the screen.
  40.     If it goes out one side it will reappear on the other.  A very easy optimization
  41.     that can be performed immediately is to replace all the far pointers with near
  42.     pointers (and recompile).  The "world" is limited to less than 64K but the
  43.     program runs about 70% faster.  If any key is pressed (except 'x') the program
  44.     will pause and display the number of generations that have passed.
  45.  
  46.     PLEASE DO NOT REMOVE THE CREDITS FROM ANY IMPROVED VERSIONS THAT ARE
  47.     DISTRIBUTED TO THE WORLD AT LARGE.
  48.  
  49. */
  50.  
  51.  
  52. #include <alloc.h>
  53. #include <stdlib.h>
  54. #include <stdio.h>
  55. #include <graphics.h>
  56.  
  57. typedef struct cell {            /* each of these replaces an array element*/
  58.      unsigned int t:2;           /* 3-state flag: birth(3),death(2),nc(0)  */
  59.      unsigned int neighbors:5;   /* 5-bit num field, holds n-hood info     */
  60.      unsigned int age:9;         /* 9 bits left to play with (use for age?)*/
  61.      unsigned int x;             /* x coordinate of cell                   */
  62.      struct cell far *NextCell;  /* pointer to next cell                   */
  63. } CELL, far *CELLPTR;
  64.  
  65.  
  66. typedef struct row {
  67.      unsigned int y;
  68.     CELLPTR FirstCell;
  69.     struct row far *NextRow;
  70. } ROW, far *ROWPTR;
  71.  
  72.  
  73. /********************
  74.  * GLOBAL variables *
  75.  ********************/
  76.  
  77. ROWPTR FirstRow;
  78. CELLPTR top;    /* top of stack of unused cells */
  79. ROW ROI[3];
  80.  
  81. unsigned char MAXCOLOR;         /* these 3 variables are semi-con- */
  82. unsigned int MAXROW, MAXCOL;    /* stant; they are assigned once   */
  83.  
  84. unsigned int n;                 /* the number of generations       */
  85.  
  86.  
  87. /************************
  88.  * Function Definitions *
  89.  ************************/
  90.  
  91.  
  92.      void credits(){
  93.  
  94.  
  95.      printf("\tThis implementation of Conway's Life simulation was coded\n");
  96.      printf("\tusing an algorithm hinted at by J. Francis, on the Usenet\n");
  97.      printf("\tforum, rec.games.programmer, on Jan 25, 1988.\n");
  98.      printf("\n\t\t\t\t  by\n");
  99.      printf("\t*****************************************************\n");
  100.      printf("\t*                  Copyright 1989                   *\n");
  101.      printf("\t*  Anibal Antonio Acero         (312) 702-7234      *\n");
  102.      printf("\t*  5513 S. Everett Ave.     acero@tank.uchicago.edu *\n");
  103.      printf("\t*  Chicago, IL 60637         ace3@tank.uchicago.edu *\n");
  104.      printf("\t*                                                   *\n");
  105.      printf("\t*         LIFE for IBM PC/AT etc. ver 1.0           *\n");
  106.      printf("\t*                 May 11, 1989                      *\n");
  107.      printf("\t*                                                   *\n");
  108.      printf("\t* This program may be freely copied.  It MAY NOT be *\n");
  109.      printf("\t* used in ANY commercial venture.  Please send sug- *\n");
  110.      printf("\t* gestions, improvements, comments, etc., to the    *\n");
  111.      printf("\t* address above.  Enjoy!                            *\n");
  112.      printf("\t*****************************************************\n\n\n");
  113. }
  114.  
  115. void initgraf(){
  116.      CELLPTR tmp;
  117.      int graphdriver=DETECT;
  118.      int graphmode;
  119.  
  120.      if (registerbgidriver(EGAVGA_driver) < 0) exit(1);
  121.      if (registerbgidriver(Herc_driver) < 0) exit(1);
  122.      if (registerbgidriver(CGA_driver) < 0) exit(1);
  123.      credits();  /* show something interesting during stack initialization */
  124.  
  125.      top=farmalloc(sizeof(CELL));  /* create stack of cells */
  126.      top->NextCell=NULL;           /* last in, first out */
  127.      while (farcoreleft() > 15000){/* save 15K for rows and other bookkeeping */
  128.          tmp=top;
  129.          top=farmalloc(sizeof(CELL));
  130.          top->NextCell=tmp;
  131.      }
  132.      initgraph(&graphdriver,&graphmode,"");
  133.  
  134.      MAXCOLOR=getmaxcolor()+1;
  135.      MAXCOL=getmaxx();
  136.      MAXROW=getmaxy();
  137.  
  138. }/* end initgraf */
  139.  
  140. CELLPTR aaamalloc(){ /* set address of new cell from top of stack */
  141.                   CELLPTR tmp;
  142.  
  143.                   if (top!=NULL){
  144.                       tmp=top;
  145.                       top=top->NextCell;
  146.                       return(tmp);
  147.                   }
  148.                   else
  149.                       exit(1);  /* not enough memory */
  150. }
  151.  
  152. void aaafree(CELLPTR pcell){  /* add dead cell to top of stack */
  153.  
  154.              pcell->NextCell=top;
  155.              top=pcell;
  156. }
  157.  
  158. CELLPTR new_cell(unsigned int x){
  159.                  CELLPTR tempc;
  160.  
  161.                  tempc=aaamalloc();
  162.                  tempc->x=x;
  163.                  tempc->t=0;
  164.                  tempc->neighbors=0;
  165.                  tempc->NextCell=NULL;
  166.                  return (tempc);
  167. }
  168.  
  169. ROWPTR new_row(ROWPTR next, unsigned int x, unsigned int y){
  170.                ROWPTR temp;
  171.  
  172.                temp=farmalloc(sizeof(ROW));
  173.                temp->y=y;
  174.                temp->NextRow=next;
  175.                if (x==MAXCOL) {
  176.                     temp->FirstCell=new_cell(0);
  177.                     temp->FirstCell->NextCell=new_cell(1);
  178.                     temp->FirstCell->NextCell->NextCell=new_cell(x);
  179.                }
  180.                else if (x==(MAXCOL-1)){
  181.                     temp->FirstCell=new_cell(0);
  182.                     temp->FirstCell->NextCell=new_cell(x);
  183.                     temp->FirstCell->NextCell->NextCell=new_cell(x+1);
  184.                }
  185.                else{
  186.                     temp->FirstCell=new_cell(x);
  187.                     temp->FirstCell->NextCell=new_cell(x+1);
  188.                     temp->FirstCell->NextCell->NextCell=new_cell(x+2);
  189.                } /* end if */
  190.                return(temp);
  191. }
  192.  
  193. CELLPTR find_cell(ROW try, unsigned int x, unsigned int y){
  194.               ROWPTR crow;
  195.               ROWPTR prow;
  196.               CELLPTR ccell;
  197.               CELLPTR pcell;
  198.  
  199.               if (try.FirstCell == NULL){
  200.                   if (try.NextRow == NULL){
  201.                       prow=crow=FirstRow;
  202.                       while (crow->y < y && crow->NextRow != NULL){
  203.                           prow=crow;
  204.                           crow=crow->NextRow;
  205.                       }
  206.                       if (crow == FirstRow && y < crow->y){
  207.                           try.NextRow=FirstRow=new_row(crow,x,y);
  208.                           crow=FirstRow;
  209.                       }
  210.                       else if (crow->NextRow == NULL && y > crow->y){
  211.                           try.NextRow=crow->NextRow=new_row(NULL,x,y);
  212.                           crow=crow->NextRow;
  213.                       }
  214.                       else if (y < crow->y){
  215.                           try.NextRow=prow->NextRow=new_row(prow->NextRow,x,y);
  216.                           crow=prow->NextRow;
  217.                       }
  218.                       else try.NextRow=crow;
  219.                   }
  220.                   else
  221.                       crow=try.NextRow;
  222.  
  223.                   /* at this pt crow points at the row which
  224.                      contains the cell sought, if it exists  */
  225.  
  226.                   pcell=ccell=crow->FirstCell;
  227.               }  /* start at the beginning of the row */
  228.               else
  229.                   pcell=ccell=try.FirstCell;
  230.  
  231.               while (ccell->x < x && ccell->NextCell != NULL){
  232.                   pcell=ccell;
  233.                   ccell=ccell->NextCell;
  234.               }
  235.               if (ccell == crow->FirstCell && x < ccell->x){
  236.                   crow->FirstCell=new_cell(x);
  237.                   crow->FirstCell->NextCell=ccell;
  238.                   return (crow->FirstCell);
  239.               }
  240.               else if (ccell->NextCell == NULL && x > ccell->x)
  241.                   return(ccell->NextCell=new_cell(x));
  242.               else if (x < ccell->x){
  243.                   pcell->NextCell=new_cell(x);
  244.                   pcell->NextCell->NextCell=ccell;
  245.                   return(pcell->NextCell);
  246.               }
  247.               return (ccell);
  248. } /* find_cell */
  249.  
  250.  
  251. void do_neighbors(CELLPTR ccell){
  252.      unsigned int x;
  253.      char t,i;
  254.  
  255.      x=ccell->x;
  256.  
  257.      if (ccell->t == 3)  t=2;
  258.      else t = -2;
  259.  
  260.      if (x==0){
  261.          for (i=0; i < 3; i++){
  262.              ROI[i].FirstCell=find_cell(ROI[i],0,ROI[i].y);
  263.              if (i != 1)
  264.                  ROI[i].FirstCell->neighbors+=t;
  265.              if (ROI[i].FirstCell->NextCell==NULL || ROI[i].FirstCell->NextCell->x != 1)
  266.                  ROI[i].FirstCell->NextCell=find_cell(ROI[i],1,ROI[i].y);
  267.              ROI[i].FirstCell->NextCell->neighbors+=t;   /* don't do current cell */
  268.              ROI[i].FirstCell=NULL;
  269.              find_cell(ROI[i],MAXCOL,ROI[i].y)->neighbors+=t;
  270.              ROI[i].FirstCell=NULL;
  271.          }
  272.          return;
  273.      }
  274.      if (x == MAXCOL){
  275.          for (i=0; i < 3; i++){
  276.               if (ROI[i].FirstCell==NULL || ROI[i].FirstCell->x != (x-1))
  277.                   ROI[i].FirstCell=find_cell(ROI[i],x-1,ROI[i].y);
  278.               ROI[i].FirstCell->neighbors+=t;
  279.               if (ROI[i].FirstCell->NextCell==NULL || ROI[i].FirstCell->NextCell->x != x)
  280.                       ROI[i].FirstCell->NextCell=find_cell(ROI[i],x,ROI[i].y);
  281.               if (i != 1)
  282.                   ROI[i].FirstCell->NextCell->neighbors+=t;
  283.               ROI[i].FirstCell=NULL;
  284.               ROI[i].FirstCell=find_cell(ROI[i],0,ROI[i].y);
  285.               ROI[i].FirstCell->neighbors+=t;
  286.               }
  287.          return;
  288.          }
  289.  
  290.      for (i=0; i < 3; i++){
  291.          if (ROI[i].FirstCell==NULL || ROI[i].FirstCell->x != (x-1))
  292.              ROI[i].FirstCell=find_cell(ROI[i],x-1,ROI[i].y);
  293.          ROI[i].FirstCell->neighbors+=t;
  294.          if (ROI[i].FirstCell->NextCell->x != x)
  295.              ROI[i].FirstCell=find_cell(ROI[i],x,ROI[i].y);
  296.          else ROI[i].FirstCell=ROI[i].FirstCell->NextCell;
  297.          if (i != 1)
  298.              ROI[i].FirstCell->neighbors+=t;
  299.          if (ROI[i].FirstCell->NextCell->x != (x+1))
  300.              ROI[i].FirstCell->NextCell=find_cell(ROI[i],x+1,ROI[i].y);
  301.          ROI[i].FirstCell->NextCell->neighbors+=t;
  302.    }
  303. }
  304.  
  305.  
  306. void find_changers(){
  307.                   ROWPTR crow;
  308.                   CELLPTR ccell;
  309.                   unsigned char color;
  310.                   
  311.                   color=n%MAXCOLOR;
  312.                   /* cycle thru colors to give sense of time */
  313.                   if (!color) color=9%MAXCOLOR;
  314.  
  315.                   crow=FirstRow;
  316.  
  317.  
  318.                   while (crow != NULL){
  319.  
  320.                       ccell=crow->FirstCell;
  321.  
  322. /* initialize ROI*/   ROI[0].NextRow=NULL;
  323. /* dont know FC  */   ROI[0].FirstCell=NULL;
  324. /* do know y val */   if (!crow->y) ROI[0].y=MAXROW;
  325.                       else ROI[0].y=crow->y-1;
  326.  
  327.                       ROI[1].NextRow=crow;
  328.                       ROI[1].FirstCell=NULL;
  329.                       ROI[1].y=crow->y;
  330.  
  331.                       ROI[2].NextRow=NULL;
  332.                       ROI[2].FirstCell=NULL;
  333.                       if (crow->y==MAXROW) ROI[2].y=0;
  334.                       else ROI[2].y=crow->y+1;
  335.  
  336.  
  337.                       while(ccell != NULL){
  338.                           if (ccell->t){
  339.                               do_neighbors(ccell);
  340.                               if (ccell->t == 2){
  341.                                   (ccell->neighbors)--;
  342.                                   putpixel(ccell->x,crow->y,0);
  343.                               }
  344.                               else {
  345.                                   (ccell->neighbors)++;
  346.                                   putpixel(ccell->x,crow->y,color);
  347.                               }
  348.                               ccell->t=0;
  349.                           }
  350.                           ccell=ccell->NextCell;
  351.                       }
  352.                       crow=crow->NextRow;
  353.                   }
  354. }
  355.  
  356. void update_world(){
  357.                   ROWPTR crow, prow;
  358.                   CELLPTR ccell, pcell;
  359.  
  360.                   crow=prow=FirstRow;
  361.                   while (crow != NULL){
  362.                       pcell=ccell=crow->FirstCell;
  363.  
  364.                       /* while n=0 of FirstCell       */
  365.                       /* update pointer to first cell */
  366.                       /* free mem of unused cell      */
  367.                       /* re-establish first */
  368.                       while (ccell != NULL  && !(ccell->neighbors)){
  369.                           ccell=ccell->NextCell;
  370.                           aaafree(pcell);
  371.                           crow->FirstCell=pcell=ccell;
  372.                       }
  373.  
  374.                       while (ccell != NULL){
  375.                           switch(ccell->neighbors){
  376.                           case 0:
  377.                                   pcell->NextCell=ccell->NextCell;
  378.                                   aaafree(ccell);
  379.                                   ccell = NULL;
  380.                                   break;
  381.                           case 6: /* cell born */
  382.                                   ccell->t=3;
  383.                                   break;
  384.                           case 1:    /*  cell  */
  385.                           case 9:
  386.                           case 3:    /*  dies  */
  387.                           case 11:
  388.                           case 13:   /*  next  */
  389.                           case 15:
  390.                           case 17:   /*  time  */
  391.                                   ccell->t=2;
  392.                           } /* end switch */
  393.  
  394.                           if (ccell==NULL)
  395.                               ccell=pcell->NextCell;
  396.                           else {
  397.                               pcell=ccell;
  398.                               ccell=ccell->NextCell;
  399.                           }
  400.                       }
  401.                   if (crow->FirstCell == NULL){
  402.                       if (crow == FirstRow){
  403.                           FirstRow=crow->NextRow;
  404.                           farfree(crow);
  405.                           crow=FirstRow;
  406.                       }
  407.                       else{
  408.                           prow->NextRow=crow->NextRow;
  409.                           farfree(crow);
  410.                           crow=prow->NextRow;
  411.                       }
  412.                   }
  413.                   else{
  414.                       prow=crow;
  415.                       crow=crow->NextRow;
  416.                   }
  417.               }
  418. }  /* end update_world */
  419.  
  420.  
  421. void r_pent(){
  422.             CELLPTR temp;
  423.  
  424.             FirstRow->y=MAXROW/2-1;
  425.             FirstRow->FirstCell->x=MAXCOL/2;
  426.             FirstRow->FirstCell->t=3;
  427.  
  428.             temp=find_cell(ROI[0],MAXCOL/2,MAXROW/2); temp->t=3;
  429.             ROI[0].NextRow=NULL;
  430.             temp=find_cell(ROI[0],MAXCOL/2,MAXROW/2+1); temp->t=3;
  431.             ROI[0].NextRow=NULL;
  432.             temp=find_cell(ROI[0],MAXCOL/2-1,MAXROW/2); temp->t=3;
  433.             ROI[0].NextRow=NULL;
  434.             temp=find_cell(ROI[0],MAXCOL/2+1,MAXROW/2-1); temp->t=3;
  435. }
  436.  
  437.  
  438. void initworld(int argc, char *argv[]){
  439.      /* open file with x,y coordinates of cells */
  440.      /* or default to r-pentomino if no args    */
  441.      CELLPTR tmp;
  442.      FILE *life;
  443.      unsigned int c,x,y;
  444.  
  445.  
  446.      FirstRow=new_row(NULL,0,0);
  447.      for (c=0; c<3; c++){ /* Initialize Region of Interest */
  448.          ROI[c].y=0;
  449.          ROI[c].FirstCell=NULL;
  450.          ROI[c].NextRow=NULL;
  451.      }
  452.  
  453.      if (argc > 1) {
  454.           life=fopen(argv[1],"r");
  455.           if (life==NULL){
  456.               outtext(argv[1]);
  457.               outtext(" not found!");
  458.               outtextxy(1,10,"Continuing with default start-up: one r-pentomino");
  459.               delay(2000);
  460.               clearviewport();
  461.               r_pent();
  462.               return;
  463.           }
  464.           c=fscanf(life, "%d %d", &x,&y);
  465.           FirstRow->y=y;
  466.           FirstRow->FirstCell->x=x;   /* initialize first cell */
  467.           FirstRow->FirstCell->t=3;
  468.           while (c!=EOF){
  469.               tmp=find_cell(ROI[0],x,y);
  470.               tmp->t=3;
  471.               ROI[0].NextRow=NULL;
  472.               c=fscanf(life, "%d %d", &x,&y);
  473.           }
  474.           c=fclose(life);
  475.      }
  476.      else
  477.           r_pent();
  478. }/* end initworld */
  479.  
  480. main (int argc, char *argv[]) {
  481.      unsigned done=0,size;
  482.      void far *buffer;
  483.      char c[5];
  484.  
  485.      initgraf();
  486.      size=imagesize(0,0,MAXCOL,8);
  487.      buffer=farmalloc(size);
  488.  
  489.      initworld(argc,argv);  /* place cells in list */
  490.  
  491.      while (!done){
  492.           ++n;
  493.           find_changers();
  494.           update_world();
  495.           if (kbhit()){
  496.                if ((*c=getch())=='x') done=1;
  497.                else{
  498.                      getimage(0,MAXROW-7,MAXCOL,MAXROW,buffer);
  499.                      putimage(0,MAXROW-7,buffer,XOR_PUT);
  500.                      moveto(MAXCOL/5,MAXROW-7);
  501.                      outtext(itoa(n,c,10));
  502.                      outtext(" generations; Space bar to continue, x to quit ");
  503.                      while(!kbhit());
  504.                      if ((*c=getch())=='x') done=1;
  505.                      putimage(0,MAXROW-7,buffer,COPY_PUT);
  506.                }
  507.           }
  508.      }
  509.      closegraph();
  510.      printf("\t\t\t%d generations\n\n",n);
  511.      credits();
  512.  
  513. }/* end main */
  514.